package com.love.labuladong.twopoint.slidewindow;

import java.util.Arrays;

/**
 * @Author : zh
 * @Description : 992 K个不同整数的子数组
 * @Date : 2024-09-03 16:09
 */
public class SubArraysWithKDistinct992 {


    public static int MANX = 20001;

    // 记录每个数的词频
    public static int[] cnts = new int[MANX];

    // arr 中有多少子数组，数字种类不超过k
    // arr的长度是n,arr里的数值 1 ~ n之间
    public static int numsOfMostKinds(int[] arr,int k){
        Arrays.fill(cnts,1,arr.length + 1,0);
        int ans = 0;
        // collect ： 收集到的数的种类
        for (int l = 0,r = 0,collect = 0; r < arr.length; r++){
            // r (刚进)
            if(++cnts[arr[r]] == 1){ // 新的数
                collect++;
            }
            // l ... r 要求超过k种，已经 k+1种，l往右（吐数字）
            while (collect > k){
                if(--cnts[arr[l++]] == 0){
                    collect--;
                }
            }
            // while出来。 l ... r 不超过k种数字
            // 0...3
            // 0 ~ 3
            // 1 ~ 3
            // 2 ~ 3
            // 3 ~ 3
            ans += r - l + 1;
        }
        return ans;
    }


    public static int subArraysWithDistinct(int[] arr,int k){
        return numsOfMostKinds(arr,k) - numsOfMostKinds(arr,k - 1);
    }





}
